/**
 * 72. 编辑距离
 * https://leetcode-cn.com/problems/edit-distance/
 */
public class Solutions_72 {
    public static void main(String[] args) {
        String word1 = "horse", word2 = "ros";  // output: 3
        // horse -> rorse (将 'h' 替换为 'r')
        // rorse -> rose (删除 'r')
        // rose -> ros (删除 'e')

//        String word1 = "intention", word2 = "execution";  // output: 5
        // intention -> inention (删除 't')
        // inention -> enention (将 'i' 替换为 'e')
        // enention -> exention (将 'n' 替换为 'x')
        // exention -> exection (将 'n' 替换为 'c')
        // exection -> execution (插入 'u')

        int result = minDistance(word1, word2);
        System.out.println(result);
    }

    public static int minDistance(String word1, String word2) {
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        int len1 = arr1.length;
        int len2 = arr2.length;
        // dp[1][1] = 1：表示 word1 中的前一个字符转换成 word1 中的前一个字符最少需要 1 步
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 初始化 dp，设置 dp 默认值（为之后的计算，提供已知结果）
        for (int i = 0; i <= len2; i++) {
            // word1 字符串长度为 0 时，word1 要转换成 word2 字符串最少需要的转换次数
            // 主要为 i 次增加操作
            dp[0][i] = i;
        }
        for (int i = 0; i <= len1; i++) {
            // word2 字符串长度为 0 时，word1 要转换成 word2 字符串最少需要的转换次数
            // 主要为 i 次删除操作
            dp[i][0] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (arr1[i - 1] == arr2[j - 1]) {
                    // [0, i) 字符串与 [0, j) 字符串相等时，即不用进行删除，增加，替换操作
                    // 取 [0, i - 1) 字符串转换成 [0, j - 1) 字符串的操作次数即可
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 不相等时，最少需要进行一次操作
                    // 可以是删除，可以是修改，可以是增加，但是最少要进行一步操作
                    // 增加时，选择 dp[i][j - 1] 结果
                    // 修改时，选择 dp[i - 1][j - 1] 结果
                    // 删除时，选择 dp[i - 1][j] 结果
                    // 选择操作次数最少的，再加上本次进行的一次操作
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                }
            }
        }
        // 最终，即是字符串 word1 转换成 word2 最少需要的次数
        return dp[len1][len2];
    }
}
